package org.xqh.study.leetcode.algorithm.dynamicplan;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName EggDrop
 * @Description https://leetcode-cn.com/problems/super-egg-drop/
 * 鸡蛋落地
 * @Author xuqianghui
 * @Date 2021/3/2 10:50
 * @Version 1.0
 */
public class EggDrop {

    public static void main(String[] args) {
        EggDrop egg = new EggDrop();
        System.out.println(egg.superEggDrop(2, 5));
    }

    public int superEggDrop(int K, int N) {
        return dp(K, N);
    }

    Map<Integer, Integer> memo = new HashMap();
    public int dp(int K, int N) {
        if (!memo.containsKey(N * 100 + K)) {
            int ans;
            if (N == 0) {
                ans = 0;
            } else if (K == 1) {
                ans = N;
            } else {
                int lo = 1, hi = N;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(K-1, x-1);
                    int t2 = dp(K, N-x);

                    if (t1 < t2) {
                        lo = x;
                    } else if (t1 > t2) {
                        hi = x;
                    } else {
                        lo = hi = x;
                    }
                }

                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)), Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));
            }

            memo.put(N * 100 + K, ans);
        }

        return memo.get(N * 100 + K);
    }
}
